#include "bitmap.h"
#include "stdint.h"
#include "string.h"
#include "print.h"
#include "interrupt.h"
#include "debug.h"

/* 将位图btmp初始化 */
void bitmap_init(struct bitmap *btmp){
    memset(btmp->bits, 0, btmp->btmp_bytes_len);
}

/* 判断bit_idx位是否为1,若为1,则返回true,否则返回false */
bool bitmap_scan_test(struct bitmap *btmp, uint32_t bit_idx){
    uint32_t byte_idx = bit_idx / 8;
    uint32_t bit_odd = bit_idx % 8;
    return (btmp->bits[byte_idx] & (BITMAP_MASK << bit_odd));
}

/* 在位图中申请连续cnt个位,成功,则返回起始下标,失败,返回-1 */
int bitmap_scan(struct bitmap *btmp, uint32_t cnt){
    uint32_t idx_byte = 0;  //记录空闲位所在的字节
    while ((0xff == btmp->bits[idx_byte]) && (idx_byte < btmp->btmp_bytes_len)){
        // 表示该idx_byte位已经被全部分配, 0xff表示无空闲位, 找下一字节
        idx_byte++;
    }

    if (idx_byte == btmp->btmp_bytes_len){
        return -1;      //内存池中找不到可用的空间
    }

    int idx_bit = 0;
    // 在找到的该字节内, 一位一位比对, 返回空闲位的索引
    while ((uint8_t)(BITMAP_MASK << idx_bit) & btmp->bits[idx_byte]){
        idx_bit++;  // 00000001 & 00011111 --> idx_bit = 5
    }

    int bit_idx_start = idx_byte *8 + idx_bit; //空闲位在位图的下标
    if (cnt == 1){
        return bit_idx_start;
    }

    uint32_t bit_left = (btmp->btmp_bytes_len * 8 - bit_idx_start); //还有多少位可以判断
    uint32_t next_bit = bit_idx_start + 1;
    uint32_t count = 1;             //记录找到连续空闲位的个数
    bit_idx_start = -1;             //先置-1, 若找不到就返回它
    while (bit_left-- > 0){
        if (!(bitmap_scan_test(btmp, next_bit))){
            //若next_bit为0
            count++;
        } else {
            count = 0;  //不连续, 重新开始找
        }
        if (count == cnt){
            bit_idx_start = next_bit - cnt + 1;
            break;
        }
        next_bit++;
    }
    return bit_idx_start;
}

/* 将位图btmp的bit_idx位设置位value */
void bitmap_set(struct bitmap *btmp, uint32_t bit_idx, int8_t value){
    ASSERT((value == 0) || (value == 1));
    uint32_t byte_idx = bit_idx / 8;
    uint32_t bit_odd = bit_idx % 8;
    if (value){
        btmp->bits[byte_idx] |= (BITMAP_MASK << bit_odd);
    } else {
        btmp->bits[byte_idx] &= ~(BITMAP_MASK << bit_odd);
    }
}